\section{Upper bound in the weakly adaptive adversary model}
\label{sec:weakly_adaptive}

In this section, we first analyze the \symdiff~protocol starting from
a well-mixed distribution of tokens and prove
Theorem~\ref{thm:rand_sym_diff} (presented in
Section~\ref{sec:sym_diff_analysis}), and then show how to sample an
element from the symmetric difference of two sets efficiently in the
two-player communication complexity model (presented in
Section~\ref{sec:sym_diff_sampling}). However, before doing that, we
present the following lower bound that shows randomization is crucial
for the \symdiff~protocol.

\junk{The most natural protocol in this model would, perhaps, be the {\em
  set difference} (SET-DIFF) protocol: in each round, each node sends
to each of its neighbors a token that it has but the neighbor does
not. This ensures along every edge $(u,v)$, there is a token flow from
node $u$ to node $v$ as long as the set of tokens held by node $u$ is
not a subset of that held by node $v$ and vice versa. However, it is
known that it needs $\Omega(k)$ communication bits to find a token in
the set difference and thus this protocol cannot be efficient.}
% INCLUDED IN THE INTRO

\begin{theoremR}
\label{thm:det_sym_diff}
Consider the protocol DET-SYM-DIFF for $k$-gossip in the weakly
adaptive adversary model which is identical to the \symdiff~protocol
except for, in each round, the token sent along each edge $(u,v)$ is
chosen deterministically from the symmetric difference of the set of
tokens held by node $u$ and the set of tokens held by node
$v$. Starting from an initial token distribution where one node has
all the $k$ tokens and others have none, a strongly adaptive adversary
can force $\Omega(nk)$ rounds for the DET-SYM-DIFF protocol to
disseminate the $k$ tokens to the $n$ nodes.
\end{theoremR}

\iflong
\begin{proof}
Let the node $u$ start with all the tokens and nodes $v_1, \ldots,
v_{n-1}$ start with no tokens. The adversary can connect $u, v_1,
\ldots v_{n-1}$ in a line in the first round thereby guaranteeing only
node $v_1$ gets a token, say $t_1$. In the next round, the adversary
connects $u, v_2, \ldots, v_{n-1}, v_1$ in a line. In this round, node
$v_2$ and $v_{n-1}$ will both get token $t_1$.The adversary can
continue this way for $\frac{n-2}{2} + 1$ rounds, at which point all
the nodes $v_1, v_2, \ldots, v_{n-1}$ will have token $t_1$. We can
repeat this argument for all the $k$ tokens proving the lower bound of
$\Omega(nk)$.
\end{proof}
\fi
\input{sym_diff_analysis}

\input{sym_diff_sampling}






